package suanfa;

import java.util.HashSet;
import java.util.Set;

public class 相交链表 {

    public static void main(String[] args) {



    }

  /*  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        Set<ListNode> set = new HashSet<>();
        ListNode currentPoint = headA;
        // 将headA放入set
        while (currentPoint != null){
            set.add(currentPoint);
            currentPoint = currentPoint.next;
        }

        currentPoint = headB;
        while (currentPoint != null){
            if(set.contains(currentPoint)){
                return currentPoint;
            }
            currentPoint = headB.next;
        }
        return null;
    }*/

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode pointA = headA;
        ListNode pointB = headB;
        // 将headA放入set
        while (pointA != pointB){
            pointA = pointA.next != null ? pointA.next : headB;
            pointB = pointB.next != null ? pointB.next : headA;
        }
        return pointA;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

